package com.Oct_Twenty_One;

/**
 * 543. 二叉树的直径
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
 *
 *
 *
 * 2022/10/22 00:45
 */

public class Solution543 {

    int max=0;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root==null) return 0;
        dfs(root);
        return max;
    }

    int dfs(TreeNode root){
        if (root.left==null&&root.right==null)
        {
            return 0;
        }
        int leftLen=root.left==null?0:dfs(root.left)+1;
        int rightLen=root.right==null?0:dfs(root.right)+1;
        max=Math.max(max,leftLen+rightLen);
        return Math.max(leftLen,rightLen);
    }




    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

}
